/**
 * 多重背包
 * 有n种物品和一个容量为w的背包。第i种物品最多有nums[i]件可用，每件耗费的空间是weight[i] ，价值是values[i] 。
 * 求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大
 * 每件商品有限次使用，次数大于1，介于01背包和完全背包之间。
 * 只需要将次数展开，化为01背包，利用01背包的思想来做。
 * 输入：
 * 背包容量 w=10; 物品种类：n=3
 * 物品重量: weights=[1, 3, 4]
 * 每种物品的价值：values=[15, 20, 30]
 * 每种物品可用个数：nums=[2, 3, 2]
 * 输出：90
 */

const MultiBackage = (values, nums, weights, w, n) => {
  const dp = Array(w + 1).fill(0);
  for (let i = 0; i < n; i++) {
    for (let j = w; j >= weights[i]; j--) {
      for (let k = 1; k <= nums[i]; k++) {
        if (j >= k * weights[i]) {
          dp[j] = Math.max(dp[j], dp[j - k * weights[i]] + k * values[i]);
        }
      }
    }
  }
  return dp[w];
};
const n = 3;
const w = 10;
const values = [15, 20, 30];
const weights = [1, 3, 4];
const nums = [2, 3, 2];

console.log('多重背包', MultiBackage(values, nums, weights, w, n)); //90